CPE 332
Computer Engineering
Mathematics II
Week 6
Part II, Chapter 5 Random Process
MarKov Process
Chapter 6: Introduction to Queuing
• Random Process
– Stationary: สถิติไม่เปลี่ยน
– Ergodic: Ensemble Average=Time
Average
– Autocorrelation
– Cross Correlation
• ต่อ
• Counting Process
• MarKov Process
Process
• อาจจะได ้จากการสุ่มตัวอย่าง (Sampling) ของ
Continuous RP
– Uniform Sampling ด ้วย Sampling Period 𝑇𝑇 = 1
𝑓𝑓𝑠𝑠
• เราได ้ … , X −T , 𝑋𝑋 0 , 𝑋𝑋 𝑇𝑇 , 𝑋𝑋 2𝑇𝑇 , 𝑋𝑋 3𝑇𝑇 , …
• ปกติจะละ Sampling Period ไว ้ฐานที่เข ้าใจ เราได ้
… , 𝑋𝑋 −1 , 𝑋𝑋 0 , 𝑋𝑋 1 , 𝑋𝑋 2 , 𝑋𝑋 3 , …
• มักจะเขียนในลักษณะ 𝑋𝑋 𝑛𝑛 ; 𝑛𝑛 = 𝑖𝑖𝑛𝑛𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖
𝑋𝑋(−8) 𝑋𝑋(−7) 𝑋𝑋(−6) 𝑋𝑋(−5) 𝑋𝑋(−4) 𝑋𝑋(−3) 𝑋𝑋(−2) 𝑋𝑋(−1)
𝑋𝑋(1) 𝑋𝑋(2) 𝑋𝑋(3) 𝑋𝑋(4) 𝑋𝑋(5) 𝑋𝑋(6)
𝑋𝑋(7)
𝑋𝑋(0)
จําก ัด Sequence ความยาว N
• ค่า Autocorrelation สําหรับ N Samples
– สมการจะลดรูป เหลือแค่ Sum และเฉลี่ย N
Point แต่จะเกิดการ Biased เพราะเราเฉลี่ย
น ้อยกว่านั้น
Sequence ท่ัวไป
��દ્ધઙ્ખ Correlation
• 1. ด ้วยวิธีกราฟ
– X(n) คูณ X(n+m) คือ X(n) ที่เลื่อนไปซ ้าย m
ตําแหน่ง
• X(n-m) จะเลื่อนไปด ้านขวาแทน
– จากนั้นทําการคูณตัวอย่างที่ตําแหน่งเดียวกัน
และจับผลลัพธ์มาบวกกัน(Summation)
– ถ ้าเป็น Autocorrelation ทําแค่ครึ่งเดียว
เพราะ Rxx(m) เป็น Even Function
• Cross Correlation ต ้องทําทั้งสองด ้าน
��દ્ધઙ્ખ Correlation
• 2. ด ้วยการแตก Summation
– 𝑅𝑅
∞
𝑋𝑋𝑋𝑋 𝑚𝑚 = ∑𝑛𝑛=−∞ 𝑥𝑥 𝑛𝑛 𝑥𝑥(𝑛𝑛 + 𝑚𝑚) = 𝑅𝑅𝑋𝑋𝑋𝑋 −𝑚𝑚
– 𝑅𝑅
∞
𝑋𝑋𝑌𝑌 ±𝑚𝑚 = ∑𝑛𝑛=−∞ 𝑥𝑥 𝑛𝑛 𝑦𝑦(𝑛𝑛 ± 𝑚𝑚), not Even
– Index ของ Summation จะสิ้นสุดแค่ Index ของ
x(n) ก็พอ เพราะที่เหลือจะเป็น ศูนย์
– เช่น x(n) = {2, 1, -1 ,3}, y(n) = {1,2,1,-1,-3,4,5}
-1 0 1 2
-3 -2 -1 0 1 2 3
– 𝑅𝑅
2
𝑋𝑋𝑋𝑋 2 = ∑𝑛𝑛=−1 𝑥𝑥 𝑛𝑛 𝑥𝑥 𝑛𝑛 + 2 = 𝑅𝑅𝑋𝑋𝑋𝑋 −2
• = 𝑥𝑥 −1 𝑥𝑥 1 + 𝑥𝑥 0 𝑥𝑥 2 + 𝑥𝑥 1 𝑥𝑥 3 + 𝑥𝑥 2 𝑥𝑥 4
• = 2 −1 + 1 3 + −1 ∙ 0 + 3 ∙ 0 = 1 = 𝑅𝑅𝑋𝑋𝑋𝑋(−2)
– 𝑅𝑅
2
𝑋𝑋𝑌𝑌(−1) = ∑𝑛𝑛=−1 𝑥𝑥 𝑛𝑛 𝑦𝑦 𝑛𝑛 − 1 ≠ 𝑅𝑅𝑋𝑋𝑌𝑌(1)
• = 𝑥𝑥 −1 𝑦𝑦 −2 + 𝑥𝑥 0 𝑦𝑦 −1 + 𝑥𝑥 1 𝑦𝑦 0 + 𝑥𝑥 2 𝑦𝑦 1
• = 2 ∙ 2 + 1 ∙ 1 + −1 ∙ −1 + 3 ∙ −3 = −3
ઠ્ઠ �
હ્યદ્નદ્બ
• Counting Process
• Birth and Death Process
• Poisson Process
• MarKov Process
• MarKov Chain
Counting Process
N(t)
t
Poisson Process
• ถ ้าแต่ละเหตุการณ์ที่เกิดขึ้นเป็น Random
และไม่ขึ้นต่อกัน มันจะเป็น Poisson
– Probability ที่จะมี k เหตุการณ์เกิดในช่วงเวลา
t สามารถคํานวณได ้จากสูตร (ดูหน้าถัดไป)
– ระยะเวลาระหว่างสองเหตุการณ์ที่เกิดขึ้น เรียก
Inter-arrival time, 𝜏𝜏, จะมีการกระจายแบบ
Exponential ด ้วยค่าเฉลี่ย 1/λ,
• 𝐹𝐹𝑋𝑋 𝜏𝜏 = 𝑃𝑃 𝑋𝑋 ≤ 𝜏𝜏 = 1−𝜆𝜆𝑒𝑒−𝜆𝜆𝜏𝜏, 𝑓𝑓𝑋𝑋 𝜏𝜏 = 𝜆𝜆𝑖𝑖−𝜆𝜆𝜏𝜏
Poisson Process
Birth and Death Process
• พิจารณาจากระบบ มีทั้ง Birth ด ้วย Birth Rate
λ( t) และ Death ด ้วย Death Rate µ( t)
– เมื่อเราให ้ระบบทํางาน ในระบบจะไม่มีอะไรอยู่ เรา
เรียกว่าอยู่ที่ State 0
– เมื่อมีหนึ่ง Event เข ้ามา หรือ Birth ระบบจะมี Event
เพิ่มขึ้นและจะไปอยู่ที่ State ที่มากกว่าปัจจุบัน “หนึ่ง”
– เมื่อมีหนึ่ง Event จบลง (Death) ระบบจะลด State ลง
หนึ่ง
– ค่า State ของระบบคือจํานวน Event ที่มีอยู่ในระบบ
– การกระโดดไปยัง State ที่สูงกว่า หรือตํ่ากว่า สามารถ
กําหนดด ้วย Probability และเขียนได ้ในลักษณะของ
State Diagram
• ถ ้าระบบไม่มีการจดจํา เราเรียก Diagram นี้เป็น MarKov Model
• ระบบคือ MarKov Process
• การ Transition จาก State หนึ่ง ไปอีก State หนึ่ง กําหนดได ้
โดยค่า Probability ที่คงที่
MarKov Process and Markov Chain
xn-2
x
n-1
x
n
xn+1
xn+2
Markov Process and Markov Chain
n-2
n-1
n
n+1
n+2
• สําหรับ MarKov Chain (Discrete State แต่
Time อาจจะเป็น Continuous หรือ Discrete)
– ในขั้นนี้ เราจะเน้นที่ Discrete Time Markov Chain
– สมมุติแกนเวลา ถูกแบ่งเป็น Time Slot ที่เท่ากัน
และเราอยู่ที่ State i ใน Time Slot ปัจจุบัน ดังนั้น
จะมีเหตุการณ์เกิดได ้ดังนี้
• ระบบอยู่ที่ State เดิม ใน Time Slot หน ้า ด ้วยค่า
Probability 𝑃𝑃𝑖𝑖𝑖𝑖
• ระบบมีการเปลี่ยน State ไปยัง State อื่นๆ ด ้วยค่า
Probability 𝑃𝑃𝑖𝑖𝑖𝑖; 𝑗𝑗 = 0,1,2, … , 𝑁𝑁, 𝑗𝑗 ≠ 𝑖𝑖
Note: Continuous Time MarKov Chain สามารถ Model จาก Discrete Time
MarKov Chain โดยให้ Limit ระยะห่างของ Time Slot เข้าสู่ศูนย์
Discrete Time Markov Chain
ในรูปไม่ได ้แสดง Transition หมดทุกเส ้น
𝑃𝑃0,4
𝑃𝑃0,3
𝑃𝑃0,2
𝑃𝑃0,0
𝑃𝑃1,1
𝑃𝑃2,2
𝑃𝑃3,3
𝑃𝑃4,4
𝑃𝑃
𝑃𝑃
𝑃𝑃
𝑃𝑃
0
0,1
3,4
1
1,2
2
2,3
3
4
𝑃𝑃1,0
𝑃𝑃2,1
𝑃𝑃3,2
𝑃𝑃4,3
𝑃𝑃2,0
𝑃𝑃4,0
𝑃𝑃3,0
Discrete Time Markov Chain
ถ้าระบบมีได้ถึง State N, (State 0,1,2,…,N),
Transition Matrix จะมีขนาด (N+1)คูณ(N+1)
Discrete Time Markov Chain
Notations: દ્ભ�દ્મ�� Discrete Time MarKov Chain
• State Probability
– คือ Probability ที่จะพบว่าระบบอยู่ที่ State ใดๆ
𝑝𝑝𝑖𝑖 = 𝑃𝑃𝑖𝑖𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑖𝑖𝑃𝑃𝑖𝑖𝑖𝑖𝑦𝑦 𝑆𝑆𝑖𝑖𝑃𝑃𝑖𝑖𝑖𝑖 = 𝑖𝑖, 𝑖𝑖 = 0,1, … , 𝑁𝑁
– ∑𝑁𝑁𝑥𝑥=0 𝑝𝑝𝑥𝑥 = 1
• Transition Probability
– คือ Probability ที่ระบบจะกระโดดจาก State
หนึ่งใน Time Slot ปัจจุบัน ไปยังอีก State หนึ่ง
ใน Time Slot หน ้า อย่าลืมว่าระบบไม่มีการจํา
– 𝑃𝑃𝑖𝑖𝑖𝑖 = 𝑃𝑃 𝑋𝑋𝑛𝑛 = 𝑖𝑖, 𝑋𝑋𝑛𝑛+1 = 𝑗𝑗 ; 𝑖𝑖, 𝑗𝑗 = 0,1, … , 𝑁𝑁
– ∑𝑁𝑁𝑖𝑖=0 𝑃𝑃𝑖𝑖𝑖𝑖 = 1
• ระบบอยู่ที่ Equilibrium ค่าเหล่านี้จะไม่เปลี่ยน
Discrete Time Markov Chain
Discrete Time Markov Chain
Discrete Time Markov Chain
Discrete Time Markov Chain
Discrete Time Markov Chain
• สถานะของระบบ ดูได ้จากจํานวณ Event ที่อยู่ในระบบ
เรียก State ของระบบ
– ถ ้า State เป็น Discrete เราได ้ MarKov Chain
• มีค่า Probability สองชุดที่อธิบายการทํางานของระบบ
– State Probability: Probability ที่ระบบจะอยู่ที่ State ใด
State หนึ่ง
• ผลรวมของ State Probability จะต ้องเท่ากับ 1
– Transition Probability: Probability ที่ระบบจะมีการเปลี่ยน
State
• อธิบายจาก Transition Matrix
• ผลรวมของ Transition Probability แต่ละแถว จะต ้องเท่ากับ 1
• ถ ้าระบบอยู่ที่ Equilibrium ค่า Probability ของ State
จะไม่เปลี่ยน และสามารถอธิบายได ้ด ้วย Global Balance
Equation
• MarKov Chain ที่เราสนใจคือ Irreducible และ
Aperiodic
Detailed Balance Equation:
Simple MarKov Chain
• Detailed Balance Equation
ระบบจะอยู่ที่ State เด ิม หร ือกระโดดไปย ัง State ข ้างเค ียงเท่าน ั�น
Markov Chain(Detailed Bal Eq)
• Detailed Balance Equation
• Transition Matrix ของ Simple Markov
Chain จะมีลักษณะเป็น Tridiagonal
P
P
0
00
01
P
P
P
10
11
12
P =
P
P
P
21
22
23
Pn− ,1 n
0
P
P
n, n−1
nn
• MarKov Chain แสดงด ้วย Markov Model
ดังรูปข ้างล่าง
– 1. จงหา Transition Matrix
– 2. จาก Transition Matrix จงคํานวณหา State
Probability
0.2
0.3
0.1
0.2
0
1
2
3
0.1
0.1
0.2
0.5
0.8
0.6
0.6
0.1
0.2
– 1. จงหา Transition Matrix
0.2
0.3
0.1
0.2
0
1
2
3
0.1
0.1
0.2
0.5
0.8
0.6
0.6
0.1
0.2
P
P
P
P
00
01
02
03
P
P
P
P
10
11
12
13
P = P P P P
20
21
22
23
P
P
P
P
30
31
32
33
– 1. จงหา Transition Matrix
0.2
0.3
0.1
0.2
0
1
2
3
0.1
0.1
0.2
0.5
0.8
0.6
0.6
0.1
0.2
P
P
P
P
00
01
02
03
5
.
0
3
.
0
0
0 2
.
P
P
P
P
10
11
12
13
P =
= 1
.
0
0 8
.
0 1
.
0
P
P
P
P
1
.
0
.
0 1
6
.
0
0 2
.
20
21
22
23
P
P
P
P
30
31
32
33
0
2
.
0
2
.
0
0 6
.
– 2. จงคํานวณหา State Probability
0.2
5
.
0
0 3
.
0
.
0 2
0.3
0.1
0.2
0
1
2
3
P = 0 1
.
8
.
0
0 1
.
0
0.1
0.1
0.2
0 1
.
1
.
0
0 6
.
.
0 2
0.5
0.8
0.6
0.6
0.1
0.2
0
2
.
0
2
.
0
.
0 6
– 2. จงคํานวณหา State Probability
0.2
5
.
0
0 3
.
0
.
0 2
0.3
0.1
0.2
0
1
2
3
P = 0 1
.
8
.
0
0 1
.
0
0.1
0.1
0.2
0 1
.
1
.
0
0 6
.
.
0 2
0.5
0.8
0.6
0.6
0.1
0.2
0
2
.
0
2
.
0
.
0 6
p + p + p + p = 1 0
.
0
1
2
3
Global B
alanced Eq
uation :
p
P
p P
j
∑∞ =
ji
∑∞ i ij
i=0, i≠ j
i=0, i≠ j
– 2. จงคํานวณหา State Probability
0.2
5
.
0
0 3
.
0
.
0 2
0.3
0.1
0.2
0
1
2
3
P = 0 1
.
8
.
0
0 1
.
0
0.1
0.1
0.2
0 1
.
1
.
0
0 6
.
.
0 2
0.5
0.8
0.6
0.6
0.1
0.2
0
2
.
0
2
.
0
.
0 6
p + p + p + p =
0
.
1
0
1
2
3
Global B
alanced Eq
uation :
p
P
p P
j
∑∞ =
ji
∑∞ i ij
i=0, i≠ j
i=0, i≠ j
p [ P + P + P ] = p P + p P + p P
0
01
02
03
1 10
2
20
3 30
– 2. จงคํานวณหา State Probability
0.2
5
.
0
0 3
.
0
.
0 2
0.3
0.1
0.2
0
1
2
3
P = 0 1
.
8
.
0
0 1
.
0
0.1
0.1
0.2
0 1
.
1
.
0
0 6
.
.
0 2
0.5
0.8
0.6
0.6
0.1
0.2
0
2
.
0
2
.
0
.
0 6
p + p + p + p =
0
.
1
0
1
2
3
Global B
alanced Eq
uation : p [ P + P + P ] = p P + p P + p P
0
01
02
03
1 10
2
20
3
30
p
P
p P
p [ P + P + P ] = p P + p P + p P
j
∑∞ =
ji
∑∞ i ij
1
10
12
13
0
01
2
21
3
31
i=0, i≠ j
i=0, i≠ j
p [ P + P + P ] = p P + p P + p P
2
20
21
23
0
02
1 12
3
32
p [ P + P + P ] = p P + p P + p P
3
30
31
32
0
03
1 13
2
23
– 2. จงคํานวณหา State Probability
0.2
5
.
0
0 3
.
0
.
0 2
0.3
0.1
0.2
0
1
2
3
P = 0 1
.
8
.
0
0 1
.
0
0.1
0.1
0.2
0 1
.
1
.
0
0 6
.
.
0 2
0.5
0.8
0.6
0.6
0.1
0.2
0
2
.
0
2
.
0
.
0 6
p + p + p + p =
0
.
1
0
1
2
3
Global B
alanced Eq
uation :
p [ 3
.
0
+ 0 +
]
2
.
0
= 1
.
0 p +
1
.
0 p + .
0 p
0
1
2
3
p
P
p P
j
∑∞ =
ji
∑∞ i ij
p [ 1
.
0 +
1
.
0 + ]
0 =
3
.
0 p +
1
.
0 p +
2
.
0 p
i=0, i≠ j
i=0, i≠ j
1
0
2
3
p [ 1
.
0 +
1
.
0 +
]
2
.
0
= .
0 p + .
0 1 p + .
0 2 p
2
0
1
3
p [0 +
2
.
0
+
]
2
.
0
= 2
.
0 p + .
0 p +
2
.
0 p
3
0
1
2
– 2. จงคํานวณหา State Probability
0.2
5
.
0
0 3
.
0
.
0 2
0.3
0.1
0.2
0
1
2
3
P = 0 1
.
8
.
0
0 1
.
0
0.1
0.1
0.2
0 1
.
1
.
0
0 6
.
.
0 2
0.5
0.8
0.6
0.6
0.1
0.2
0
2
.
0
2
.
0
.
0 6
p + p + p + p =
0
.
1
0
1
2
3
Global B
alanced Eq
uation :
− 5
.
0 p + .
0 1 p + 0.1 p
= 0
0
1
2
p
P
p P
j
∑∞ =
ji
∑∞ i ij
.
0 3 p −
2
.
0 p +
1
.
0 p +
2
.
0 p = 0
i=0, i≠ j
i=0, i≠ j
0
1
2
3
1
.
0 p −
4
.
0 p +
2
.
0 p = 0
1
2
3
2
.
0 p
+ 0 2
. p −
4
.
0 p = 0
0
2
3
Homogeneous Linear Eq. ยังแก้สมการไม่ได้
– 2. จงคํานวณหา State Probability
0.2
5
.
0
0 3
.
0
.
0 2
0.3
0.1
0.2
0
1
2
3
P = 0 1
.
8
.
0
0 1
.
0
0.1
0.1
0.2
0 1
.
1
.
0
0 6
.
.
0 2
0.5
0.8
0.6
0.6
0.1
0.2
0
2
.
0
2
.
0
.
0 6
− 5
.
0 p + .
0 1 p +
1
.
0 p
= 0
0
1
2
3
.
0 p − 0.2 p + .
0 1 p + .
0 2 p = 0
0
1
2
3
0 1
. p −
4
.
0 p + 0.2 p = 0
1
2
3
p
+ p
+ p
+ p = .
1 0
0
1
2
3
ต ้องนําสมการที่ 4 มาใส่เสมอ + อีก 3 สมการอะไรก็ได ้
สมการ Non Homogeneous System of Linear Equation
แก ้ได ้โดยวิธี Elimination จะได ้ Unique Solution
– 2. จงคํานวณหา State Probability
0.2
5
.
0
0 3
.
0
.
0 2
0.3
0.1
0.2
0
1
2
3
P = 0 1
.
8
.
0
0 1
.
0
0.1
0.1
0.2
0 1
.
1
.
0
0 6
.
.
0 2
0.5
0.8
0.6
0.6
0.1
0.2
0
2
.
0
2
.
0
.
0 6
− 0 5
. p +
1
.
0 p + 0 1
. p
= 0
p
0
1
2
− 5
.
0
1
.
0
1
.
0
0 0
0
.
0 3 p − 0 2
. p + 0 1
. p + .
0 2 p = 0
p
0
1
2
3
⇒ 3
.
0
− 2
.
0
0 1
.
.
0 2 1 = 0
1
.
0 p − .
0 4 p + 0 2
. p = 0
0
1
.
0
− 4
.
0
.
0 2 p
0
1
2
3
2
p
+ p
+ p
+ p = 1 0
.
p
0
1
2
3
1
1
1
1 3 1
Non Homogeneous System of Linear Equation
แก ้ได ้โดยวิธี Elimination จะได ้ Unique Solution
Algorithm ในการแก ้สมการ จะกล่าวภายหล ัง
– 2. จงคํานวณหา State Probability
0.2
5
.
0
0 3
.
0
.
0 2
0.3
0.1
0.2
0
1
2
3
P = 0 1
.
8
.
0
0 1
.
0
0.1
0.1
0.2
0 1
.
1
.
0
0 6
.
.
0 2
0.5
0.8
0.6
0.6
0.1
0.2
0
2
.
0
2
.
0
.
0 6
− .
0 5 p +
1
.
0 p +
1
.
0 p
= 0
)
1
(
0
1
2
( )
4 − 5× ( )
2 : − .
0 5 p + 2 p + 0 5
. p = 1
)
5
(
.
0 3 p − 2
.
0 p +
1
.
0 p + .
0 2 p = 0
(2)
0
1
2
0
1
2
3
( )
4 − 5×
)
3
(
:
p + 0.5 p + 3 p = 1 ( )
6
1
.
0 p − 4
.
0 p +
2
.
0 p = 0
)
3
(
0
1
2
1
2
3
p
+ p
+ p
+ p = 0
.
1
( )
4
จากสมการที่ (1),(5),(6) เราได ้
0
1
2
3
− 0.5 p + 0.1 p + 0.1 p = 0
)
1
(
0
1
2
− 0.5 p + 2 p
+ 0.5 p = 1
)
5
(
0
1
2
p + 0.5 p + 3 p = 1 (6)
0
1
2
– 2. จงคํานวณหา State Probability
0.2
5
.
0
0 3
.
0
.
0 2
0.3
0.1
0.2
0
1
2
3
P = 0 1
.
8
.
0
0 1
.
0
0.1
0.1
0.2
0 1
.
1
.
0
0 6
.
.
0 2
0.5
0.8
0.6
0.6
0.1
0.2
0
2
.
0
2
.
0
.
0 6
− 0 5
. p + .
0 1 p +
1
.
0 p = 0
)
1
(
0
1
2
+ ×
p +
p =
−
(6) 2
)
1
( :
.
0 7
3 2
.
1 (7)
5
.
0 p + 2 p
+ 5
.
0 p = 1
)
5
(
1
2
0
1
2
(6) + 2 ×
)
5
(
:
.
4 5 p +
4 p = 3
)
8
(
p + .
0 5 p + 3 p = 1 ( )
6
1
2
0
1
2
5
.
4
4 5
.
4 5
.
)
8
(
−
(7) : (4 −
3 )
2
.
p = 3 −
0 7
.
0 7
.
2
0 7
.
− .
3 4285714
p =
= .
0 2069
2
− .
16 57142857
– 2. จงคํานวณหา State Probability
0.2
5
.
0
0 3
.
0
.
0 2
0.3
0.1
0.2
0
1
2
3
P = 0 1
.
8
.
0
0 1
.
0
0.1
0.1
0.2
0 1
.
1
.
0
0 6
.
.
0 2
0.5
0.8
0.6
0.6
0.1
0.2
0
2
.
0
2
.
0
.
0 6
p = 0 2069
.
2
1− .
3 2 p
From (7)
:
2
p =
= 0.4828
1
.
0 7
From )
1
( : p = 0.1379
0
From ( )
4 : p = .
0 1724
3
สมการ System of Linear Equation แก ้ได ้โดยวิธี Elimination p =
137
.
0
,
9 p = 0 482
.
,
8 p = 0 206
.
,
9 p = 0 172
.
4
0
1
2
3
• MarKov Chain แสดงด ้วย Markov Model
ดังรูปข ้างล่าง
– 1. จงหา Transition Matrix
– 2. จาก Transition Matrix จงคํานวณหา
State Probability
0.5
0.1
0.3
0.2
0
1
2
3
4
0.1
0.2
0.2
0.6
0.5
0.8
0.5
0.6
0.4
• Transition Matrix
0.5
0.1
0.3
0.2
0
1
2
3
4
0.1
0.2
0.2
0.6
0.5
0.8
0.5
0.6
0.4
P
P
P
P
P
0,0
0 1
,
0,2
0,3
0,4
0 5
.
.
0 5
0
0
0
P
P
P
P
P
,
1 0
1
,
1
,
1 2
,
1 3
,
1 4
.
0 1
.
0 8
1
.
0
0
0
P == P
P
P
P
P =
2,0
2 1
,
2,2
2,3
2,4
0
0 2
.
0 5
.
.
0 3
0
P
P
P
P
P
3,0
3 1
,
3,2
3,3
3,4
0
0
2
.
0
6
.
0
0 2
.
P
P
P
P
P
4,0
4 1
,
4,2
4,3
4,4
0
0
0
.
0 6
.
0 4
• State Probability
0.5
0.1
0.3
0.2
0
1
2
3
4
0.1
0.2
0.2
0.6
0.5
0.8
0.5
0.6
0.4
P
P
P
P
P
0,0
0 1
,
0,2
0,3
0,4
5
.
0
5
.
0
0
0
0
P
P
P
P
P
,
1 0
1
,
1
,
1 2
,
1 3
,
1 4
1
.
0
0 8
.
.
0 1
0
0
P == P
P
P
P
P =
2,0
2 1
,
2,2
2,3
2,4
0
2
.
0
5
.
0
.
0 3
0
P
P
P
P
P
3,0
3 1
,
3,2
3,3
3,4
0
0
.
0 2
6
.
0
.
0 2
P
P
P
P
P
4,0
4 1
,
4,2
4,3
4,4
0
0
0
.
0 6
4
.
0
Detailed B
alance E
quation : p P = p P
i
i, j
j
j , i
p P = p P
.
0 5 p = .
0 1 p o
r p = 5 p
0 0 1
,
1
,
1 0
0
1
1
0
p P = p P
1
.
0 p = .
0 2 p o
r p = 0 5
. p = .
2 5 p
1
,
1 2
2
2 1
,
1
2
2
1
0
⇒
p P
= p P
3
.
0 p = .
0 2 p o
r p = .
1 5 p = .
3 75 p
2
2,3
3 3,2
2
3
3
2
0
1
p P
= p P
2
.
0 p = 0 6
. p o
r p =
p = .
1 25 p
3 3,4
4
4,3
3
4
4
3
3
0
• State Probability
Detailed B
alance E
quation : p P = p P
i
i, j
j
j , i
p P = p P
.
0 5 p = .
0 1 p o
r p = 5 p
0 0 1
,
1
,
1 0
0
1
1
0
p P = p P
1
.
0 p = .
0 2 p o
r p = 0 5
. p = .
2 5 p
1
,
1 2
2
2 1
,
1
2
2
1
0
⇒
p P
= p P
3
.
0 p = .
0 2 p o
r p = .
1 5 p = .
3 75 p
2
2,3
3 3,2
2
3
3
2
0
1
p P
= p P
2
.
0 p = 0 6
. p o
r p =
p = .
1 25 p
3 3,4
4
4,3
3
4
4
3
3
0
From
p + p + p + p + p = 1
0
1
2
3
4
p + 5 p +
5
.
2 p + 3 75
.
p + .
1 25 p = 1
0
0
0
0
0
p 1
[ + 5 + 2 5
. +
75
.
3
+ .
1
]
25 = 1
0
p = 0 0740
.
74
then
0
p = 0 3703
.
,
7 p =
1851
.
0
,
85 p = .
0 2777
,
78 p = .
0 092593
1
2
3
4
• State Probability
Detailed B
alance E
quation : p P = p P
i
i, j
j
j , i
p P = p P
.
0 5 p = .
0 1 p o
r p = 5 p
0 0 1
,
1
,
1 0
0
1
1
0
p P = p P
1
.
0 p = .
0 2 p o
r p = 0 5
. p = .
2 5 p
1
,
1 2
2
2 1
,
1
2
2
1
0
⇒
p P
= p P
3
.
0 p = .
0 2 p o
r p = .
1 5 p = .
3 75 p
2
2,3
3 3,2
2
3
3
2
0
1
p P
= p P
2
.
0 p = 0 6
. p o
r p =
p = .
1 25 p
3 3,4
4
4,3
3
4
4
3
3
0
From
p + p + p + p + p = 1
ใช้วิธีของ Matrix
0
1
2
3
4
0 5
. p −
1
.
0 p = 0
p
0
1
0 5
.
− 1
.
0
0
0
0 0
0
1
.
0 p − 0 2
. p = 0
p
1
2
0
1
.
0
− 2
.
0
0
0 1 0
0 3
. p − 0 2
. p = 0
⇒ 0
0
3
.
0
− .
0 2
0 p = 0
2
3
2
.
0 2 p −
6
.
0 p = 0
p
3
4
0
0
0
2
.
0
− 6
.
0 3 0
p + p + p + p + p = 1
1
1
1
1
1 p
0
1
2
3
4
4 1
• Chapter 6
– Introduction to Queuing Theory
• Homework Chapter 5 Download
– เน้นที่ Correlation ของ Stationary RP และ
การใช ้ Global/Detailed Balance Equation
ใน MarKov Chain
CPE 332
Computer Engineering
Mathematics II
Week 6
Part II, Chapter 6
Queuing System
• Birth and Death Process
• Unlimited Server
• N Servers
• Single Server, M/M/1
• Kendal Notation
• Applications
• ระบบประกอบด ้วย Input และ Output
• พิจารณาระบบที่มีการให ้บริการ(Service) แก่
ลูกค ้า (Customer)
– ลูกค ้าเข ้ามาในระบบเพื่อขอรับบริการ (Input)
– ระบบมี Resource ที่จํากัดในการให ้บริการ
– ลูกค ้า เมื่อได ้รับบริการแล ้ว ออกไปจากระบบ
(Output)
• ระบบขายของหน้าร ้าน, ระบบหน้าธนาคาร, ระบบ
การจราจร, ระบบ Operating System ใน
คอมพิวเตอร์, สถานีนํ้ามัน/แก๊ส, คิวจ่ายของ/
อาหาร, ระบบสื่อสารข ้อมูล, ระบบโทรศัพท์ และ
อื่นๆอีกมาก
Arrival Rate = λ
Departure Rate = µ
Customer
System
Customer
1. อ ัตร าการ เข ้ามาของลูกค ้า ค ือ Arrival Rate
2. อ ัตร าการ ออกไปของลูกค ้าเม ื่อได ้ร ับบร ิการ เสร็จค ือ Departure Rate
3. State ของร ะบบค ือจํานวนลูกค ้าที่อย ู่ในร ะบบ ที่ร อบร ิการ
หร ือกําล ังถูกบร ิการ
4. ถ ้าระบบไม่ม ีการจดจํา การบร ิการลูกค ้าแต่ละรายเหม ือนก ัน
และไม่ข ึ�นก ับอด ีต เราสามารถใช ้รูปแบบ MarKov Chain อธิบายระบบ
Birth Rate
Death Rate
Arrival Rate = λ
Departure Rate = µ
Customer
System
Customer
5. ถ ้าเราแบ่งช ่วงเวลาการเข ้ามาของลูกค ้าเป็นช ่วง Time Slot
และบ ันทึกเหตุการณ ์ที่เก ิดข ึ�นในแต่ละ Time Slot
a) ม ีลูกค ้าใหม ่เข ้ามา เพ ื่อขอใช ้บร ิการ ( State ของร ะบบจะเพ ิ่ม) หร ือ b) ม ีลูกค ้าที่ได ้ร ับบร ิการแล้วออกจากระบบไป ( State จะลด) หร ือ c) ไม่ม ีลูกค ้าใหม่ และไม่ม ีลูกค ้าที่ให้บร ิการเสร็จ (State คงเด ิม) 6. จาก Model ข ้อ 5 เราจะได ้ Discrete Time Markov Chain
7. ถ ้าช ่วงเวลาของ Time Slot ส ั�นมากจนกร ะท ่ังลูกค ้าที่เข ้ามา หร ือออกไป
ในช ่วงหน ึ่ง Time Slot สามารถม ีได ้แค่คนเด ียว
เราจะสามารถ Model ระบบได ้เป็น Simple MarKov Model
Queuing System
ถ ้า λ < µ ระบบจะสามารถ
เข ้าสู่ Equilibrium ได ้
Birth Rate
; Server Utilization Death Rate
𝜌𝜌 = 𝜆𝜆𝜇𝜇
Arrival Rate = λ
Departure Rate = µ
Customer
System
Customer
Queuing System
Simple MarKov Model
Birth Rate
Death Rate
λ < µ
Arrival Rate = λ
Departure Rate = µ
Customer
System
Customer
Detailed Balance Equation: 𝒑𝒑𝒊𝒊𝑷𝑷𝒊𝒊𝒊𝒊 = 𝒑𝒑𝒊𝒊𝑷𝑷𝒊𝒊𝒊𝒊
สําหร ับสอง State i, j ที่อยู่ต ิดก ันใดๆ
Queuing System
Simple MarKov Model
𝒑𝒑
Birth Rate
𝒊𝒊𝑷𝑷𝒊𝒊𝒊𝒊 = 𝒑𝒑𝒊𝒊𝑷𝑷𝒊𝒊𝒊𝒊
Death Rate
λ < µ
Arrival Rate = λ
Departure Rate = µ
Customer
System
Customer
ในที่นี�เราจะพ ิจารณ ากรณ ี
1.
ที่ลูกค ้าแต่ละรายเข ้ามาในระบบแบบ Random
และเป็น Poisson Process
2.
เวลาในการให้บร ิการของลูกค ้าแต่ละราย เป็น Random
ม ีการ กร ะจายแบบ Exponential
Simple MarKov Model
𝒑𝒑
Birth Rate
𝒊𝒊𝑷𝑷𝒊𝒊𝒊𝒊 = 𝒑𝒑𝒊𝒊𝑷𝑷𝒊𝒊𝒊𝒊
Death Rate
λ < µ
Arrival Rate = λ
Departure Rate = µ
Customer
System
Customer
Arrival: 1. Probability ที่จะม ีลูกค ้า k คนเข ้ามาในช ่วง T ว ินาที
(𝝀𝝀𝝀𝝀)𝒌𝒌𝒆𝒆𝝀𝝀𝝀𝝀
𝑷𝑷 𝒌𝒌 = 𝑷𝑷 𝑿𝑿 = 𝒌𝒌 =
𝒌𝒌!
; 𝒌𝒌 = 𝟎𝟎, 𝟏𝟏, 𝟐𝟐, …
เม ื่อ 𝝀𝝀 เป็นค ่าเฉลี่ยจํานวนลูกค ้าที่เข ้ามา ต ่อว ินาที
2. ค่า Inter-arrival Time, 𝝉𝝉 จะมีการกระจายแบบ
Exponential ด ้วยค ่าเฉล ี่ย 𝟏𝟏 𝝀𝝀
⁄
𝑷𝑷 𝝀𝝀 ≤ 𝝉𝝉 = 𝟏𝟏 − 𝝀𝝀𝒆𝒆−𝝀𝝀𝝉𝝉
Simple MarKov Model
𝒑𝒑
Birth Rate
𝒊𝒊𝑷𝑷𝒊𝒊𝒊𝒊 = 𝒑𝒑𝒊𝒊𝑷𝑷𝒊𝒊𝒊𝒊
Death Rate
λ < µ
Arrival Rate = λ
Departure Rate = µ
Customer
System
Customer
Departure: 1. เวลาเฉล ี่ยที่ลูกค ้าใช ้บร ิการ = 𝝀𝝀𝒔𝒔 (Service Time)
จะม ีการกระจายแบบ Exponential
Probability ที่ลูกค ้าจะใช ้เวลาบร ิการ น ้อยกว่าหร ือ
เท่าก ับ 𝒕𝒕 𝑷𝑷 𝝀𝝀 ≤ 𝒕𝒕 = 𝟏𝟏 − 𝟏𝟏 𝒆𝒆−𝒕𝒕 𝝀𝝀�𝒔𝒔
𝝀𝝀𝒔𝒔
2. Departure Rate ค ืออ ัตร าที่ลูกค ้าออกจากร ะบบ
เม ื่อได ้ร ับบร ิการเสร็จ(อ ัตราการให้บร ิการแก่ลูกค ้า)
𝝁𝝁 = 𝟏𝟏
𝝀𝝀𝒔𝒔
Queuing System Case 1:
Unlimited Server; No Queue
… ∞
Arrival Rate = λ
Departure Rate = µ
Customer
System
Customer
1.
ลูกค ้าที่เข ้ามา เป็น Random ด ้วยอัตราเฉล่ีย 𝜆𝜆 และมีการกระจายแบบ Poisson 2.
สมมุติว่า Customer แต่ละคนที่เข ้ามาได ้รับการ Service จากระบบทันที (ระบบมี
Server จํานวนไม่จํากัด และรับ Customer ได ้ไม่จํากัด)
3.
เวลาที่ใช ้ในการ Service เป็น เป็น Exponential ด ้วยเวลาเฉล่ีย 𝑇𝑇𝑠𝑠
4.
ระบบสามารถรับ Customer ได ้ไม่จํากัด
5.
ลูกค ้าเข ้ามาได ้ทีละคน และออกทีละคน
6.
ระบบนี้เรียก M/M/∞
Unlimited Server; No Queue
λ < µ
k
−λ
λ
x −
e
ρ ρ
e
[
P k] =
λ
p =
; ρ =
t / Ts
1
[
P T ≥
−
t] = e
; T =
k!
x
µ
s
µ
!
x
Arrival Rate = λ
Departure Rate = µ
Customer
System
Customer
1.
สมมุติว่า Customer แต่ละคนที่เข ้ามาเป็น Poisson และได ้รับการ Service จากระบบทันที
2.
เวลาที่ใช ้ในการ Service เป็น Random สมมุติว่าเป็น Exponential ด ้วยเวลาเฉลี่ย T
3.
ระบบสามารถรับ Customer ได ้ไม่จํากัด แต่เข ้ามาได ้ทีละคน และออกทีละคน
4.
ระบบนี้เรียก M/M/∞ แสดงได ้ด ้วย Simple Markov Model
5.
เราสามารถพิสูจน์ได ้ว่าค่า State Probability จะมีการกระจายแบบ Poisson p P = p P
i
ij
j
ji
0
1
2
i
j
∞
Queuing System Case 2: Lost System
Limited Server=N; No Queue
λ < µ
x
ρ / x!
k
−λ
λ
p =
e
x
N
k
ρ
[
P k] =
t / Ts
1
[
P T ≥
−
t] = e
; T =
∑
k!
s
µ
!
0 k
k =
Arrival Rate = λ
Departure Rate = µ
Customer
System, N Server
Customer
1.
สมมุติว่า Customer แต่ละคนที่เข ้ามาเป็น Poisson และได ้รับการ Service จากระบบทันที
2.
เวลาที่ใช ้ในการ Service เป็น Random สมมุติว่าเป็น Exponential ด ้วยเวลาเฉลี่ย T
3.
ระบบสามารถรับ Customer ได ้ N ถ ้าทุก Server เต็ม จะรับ Customer ใหม่ไม่ได ้ (Lost) 4.
ระบบนี้เรียก M/M/N/N แสดงได ้ด ้วย N-state Simple Markov Model 5.
State Probability จะมีการกระจายแบบ First Erlang (Erlang B) Distribution p P = p P
i
ij
j
ji
0
1
2
i
j
N
Queuing System Case 3: Delay System
Limited Server=N; With Unlimited Queue
x
ρ
λ < µ
p ; 0 ≤ x ≤ N
1
−
0
N
1
−
k
!
x
Nρ
ρ
k
−λ
λ
p =
p
x
x
=
+
N
∑
N
e
; 0
ρ
[
P k] =
N
N!( N − ρ)
k
k =
!
t / T
0
s
1
p ; x ≥ N
[
P T ≥
−
t] = e
; T =
k!
s
0
µ
N! N
Arrival Rate = λ
Departure Rate = µ
Customer
System, N Server
Customer
1.
สมมุติว่า Customer แต่ละคนที่เข ้ามาเป็น Poisson และได ้รับการ Service จากระบบทันที
2.
เวลาที่ใช ้ในการ Service เป็น Random สมมุติว่าเป็น Exponential ด ้วยเวลาเฉลี่ย T
3.
ระบบสามารถรับ Customer ได ้ไม่จํากัด แต่จะ Service ได ้สูงสุด N พร ้อมๆกัน
4.
ถ ้าทุก Server เต็ม Customer ใหม่จะต ้องรอใน Queue ในกรณีนี้จะเกิด Queuing Delay 5.
ระบบนี้เรียก M/M/N หรือ M/M/N/∞ แสดงได ้ด ้วย Simple Markov Model 6.
State Probability จะมีการกระจายแบบ Second Erlang (Erlang C) Distribution
0
1
2
N
N+1
∞
p P = p P
i
ij
j
ji
Queuing System Case 3: Delay System
Server=1; With Unlimited Queue; M/M/1
λ < µ 1
ρ
−
p =
+1
=1− ρ
0
k
−λ
λ
− ρ
e
1
(
)
[
P k] =
t / Ts
1
x
[
P T ≥
−
t] = e
; T =
k!
s
p = ρ 1
( − ρ)
µ
x
Arrival Rate = λ
Departure Rate = µ
Customer
System, 1 Server
Customer
1.
สมมุติว่า Customer แต่ละคนที่เข ้ามาเป็น Poisson และได ้รับการ Service จากระบบทันที
2.
เวลาที่ใช ้ในการ Service เป็น Random สมมุติว่าเป็น Exponential ด ้วยเวลาเฉลี่ย T
3.
ระบบสามารถรับ Customer ได ้ไม่จํากัด แต่จะ Service ได ้ครั้งละคน
4.
ถ ้าทุก Server เต็ม Customer ใหม่จะต ้องรอใน Queue ในกรณีนี้จะเกิด Queuing Delay 5.
ระบบนี้เรียก M/M/1 หรือ M/M/1/∞ แสดงได ้ด ้วย Simple Markov Model 6.
State Probability จะมีการกระจายแบบ Second Erlang (Erlang C) Distribution
0
1
2
i
j
∞
p P = p P
i
ij
j
ji
S
S
Service Rate
Arrival Rate = λ
= µ=1/Ts
Customer
S
Queue(FIFO)
Customer
S
M/M/N
Queuing System
Servers
λ
µ=1/Ts
S
Arrival = Poisson, λ
Inter Arrival Time = Exponential, 1/λ
Service Rate, µ
Service Time, Ts (1/µ) = Exponential
Queue = FIFO
1 Server
M/M/1
Queue = 0, No Delay
Queue = Delay
0
1
N+1
N+2
X
Server ว่าง Server Busy
1/Ts = service rate
arrival rate
For each server
λ
µ =1/ Ts
State = 0
No Q Delay
Queue Empty
State = 1
Delay
State = x; Queue = infinity
Customer Wait in Q
State = x; x = Q+1
Severe Delay
Queue Overflow (Full)
กรณีที่
Congestion
Queue มีขนาดจํากัด = Q
Packet Lost
(N Server); M/M/N
Queue = 0, No Delay
Queue = Delay
0
1
i
j
N
N+1
N+2
X
Server ว่าง
i Server Busy
N Server Busy
1 Server Busy
1/h = service rate
A/h=arrival rate
For each server
Maximum Service Rate
= N/h
Service Rate at State
k = k/h
State < N
No Delay
Queue Empty
State >= N
Delay
Customer Wait in Q
Limited Q
Severe Delay
Queue Overflow (Full)
Congestion
M/M/1
แต่ละ Router เชื่อมต่อกันด ้วย Logical Link เดียว
เสมือนว่ามี Transmitter ตัวเดียวในการส่งข ้อมูลผ่าน Link
สมมุติว่าคอมพิวเตอร์ที่ต่อกับ Router
ต ้องการส่งข ้อมูลถึงกัน ตามเส ้นทางที่กําหนด
ที่ Output ของ Router สามารถ Model โดยใช ้ M/M/1
Network Model (M/M/1)
ถ ้าเราให ้ทุก Model เป็น M/M/1
ดังนั้น Delay จะเป็นผลรวมของ Delay แต่ละอัน
Kendal Notation
Kendal Notation
Kendal Notation
• M/M/1 Analysis and Examples
• HW 5 Due